
\prob{006B}{幂的整除}

对于自然数$n$，有

\begin{align*}
  3 &\mid 2^n - n \\
  5 &\mid 3^n - n \\
  2 &\mid 5^n - n \\
\end{align*}

求$n$的最小值。
\problabels{yellow/数论, green/最值问题}

\ans{$n$的最小值为$47$。}

\subsection{考虑模}

基本思路：考虑$2^n \equiv n \pmod 3$，然后列表推知$n$满足的条件；其它使用同样的方法可推导$n$的最小值。

由$2 \mid 5^n - n$知$n$显然为奇数。

由$3 \mid 2^n - n$知$2^n \equiv n \pmod 3$。$2^n$模$3$的循环节为$2$，$n$模$3$的循环节为$3$，故考虑$n = 0, \dots, 5$即可。列表（表~\ref{tab:006B-mod-3}）知$n \equiv 4 \pmod 6$或$n \equiv 5 \pmod 6$。而$n$为奇数，故$n \equiv 5 \pmod 6$。

\begin{table}[hbp]
  \centering
  \begin{tabular}{cccl}
    \toprule
    $n$ & $n$模$3$ & $2^n$模$3$ & 备注 \\
    \midrule
    $0$ & $0$ & $1$ & \\
    $1$ & $1$ & $2$ & \\
    $2$ & $2$ & $1$ & \\
    $3$ & $0$ & $2$ & \\
    $4$ & $1$ & $1$ & 满足条件 \\
    $5$ & $2$ & $2$ & 满足条件 \\
    \bottomrule
  \end{tabular}
  \caption{尝试$n = 0, \dots, 5$。} \label{tab:006B-mod-3}
\end{table}

由$5 \mid 3^n - n$知$3^n \equiv n \pmod 5$。$3^n$模$5$的循环节为$4$，$n$模$5$的循环节为$5$，故考虑$n = 0, \dots, 19$即可。列表（表~\ref{tab:006B-mod-5}）知$n$模$20$为$7, 13, 14, 16$。而$n$为奇数，故$n \equiv 7 \pmod 20$或$n \equiv 13 \pmod 20$。

\begin{table}[hbp]
  \centering
  \begin{tabular}{cccl}
    \toprule
    $n$ & $n$模$5$ & $3^n$模$5$ & 备注 \\
    \midrule
    $0$ & $0$ & $1$ & \\
    $1$ & $1$ & $3$ & \\
    $2$ & $2$ & $4$ & \\
    $3$ & $3$ & $2$ & \\
    $4$ & $4$ & $1$ & \\
    $5$ & $0$ & $3$ & \\
    $6$ & $1$ & $4$ & \\
    $7$ & $2$ & $2$ & 满足条件 \\
    $8$ & $3$ & $1$ & \\
    $9$ & $4$ & $3$ & \\
    $10$ & $0$ & $4$ & \\
    $11$ & $1$ & $2$ & \\
    $12$ & $2$ & $1$ & \\
    $13$ & $3$ & $3$ & 满足条件 \\
    $14$ & $4$ & $4$ & 满足条件 \\
    $15$ & $0$ & $2$ & \\
    $16$ & $1$ & $1$ & 满足条件 \\
    $17$ & $2$ & $3$ & \\
    $18$ & $3$ & $4$ & \\
    $19$ & $4$ & $2$ & \\
    \bottomrule
  \end{tabular}
  \caption{尝试$n = 0, \dots, 19$。} \label{tab:006B-mod-5}
\end{table}

故此数模$6$为$5$，模$20$为$7$或$13$。因此，此数最小为$47$。经检验，$n = 47$满足题设条件。
